package question4;

import com.sun.org.apache.bcel.internal.generic.NEW;

public class Offer12 {

    boolean[][] visit;

    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                visit = new boolean[board.length][board[0].length];
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean dfs(char[][] board, String word, int index, int row, int col) {
        if (row >= board.length || row < 0 || col >= board[0].length || col < 0 || index >= word.length()
            || word.charAt(index) != board[row][col] || visit[row][col]) {
            return false;
        }
        if (index == word.length() -1 ) {
            return true;
        }
        visit[row][col] = true;
        //不能用 ++index ，不然每次递归都会加1，回退的时候也不会减回去，导致index一直增加
        boolean result = dfs(board, word, index+1, row+1, col)
                        || dfs(board, word, index+1, row-1, col)
                        || dfs(board, word, index+1, row, col+1)
                        || dfs(board, word, index+1, row, col-1);
        return result;
    }

    public static void main(String[] args) {
        char[][] board = {{'A', 'B', 'C', 'E'},{'S', 'F', 'C', 'S'}};
        String word = "ABCCFS";
        boolean exist = new Offer12().exist(board, word);
        System.out.println(exist);
    }
}
